/*
 * @lc app=leetcode.cn id=74 lang=typescript
 *
 * [74] 搜索二维矩阵
 */

// @lc code=start
function searchMatrix(matrix: number[][], target: number): boolean {
  const row = matrix.length - 1;
  const column = matrix[0].length - 1;
  // find row
  let row_start = 0;
  let row_end = row;
  while (row_start <= row_end) {
    let mid = row_start + Math.floor((row_end - row_start) / 2);
    if (matrix[mid][0] === target) return true;
    if (target > matrix[mid][0]) row_start = mid + 1;
    else row_end = mid - 1;
  }

  if (row_end < 0) return false;
  const target_row = row_end;

  let column_start = 0;
  let column_end = column;
  while (column_start <= column_end) {
    let mid = column_start + Math.floor((column_end - column_start) / 2);
    if (matrix[target_row][mid] === target) return true;
    if (target > matrix[target_row][mid]) column_start = mid + 1;
    else column_end = mid - 1;
  }

  return false;
}
// @lc code=end
